package arrays.二分查找;

import java.util.HashMap;

//leetcode submit region begin(Prohibit modification and deletion)
class 二分查找704 {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] == target) {
                return mid;
            }
        }
        return -1;
    }

    public static String minWindow(String s, String t) {
        //滑动窗口符合条件字符的统计情况
        HashMap<Character, Integer> window = new HashMap<>();
        //定义需要寻找的字符和对应的字符个数
        HashMap<Character, Integer> target = new HashMap<>();
        for (char c : t.toCharArray()) {
            target.put(c, target.getOrDefault(c, 0) + 1);
        }
        //窗口的起点和结束
        int left = 0; //窗口开始位置
        int right = 0; //窗口结束位置
        int valid = 0; //字符出现的次数都满足的数量，比如t中字符a出现3次，那么s中出现3次，valid才+1
        int strLength = Integer.MAX_VALUE; //字符长度
        int start = 0;

        //先遍历到窗口的右侧包含所有的字符
        while (right < s.length()) {
            //当前遍历到的字符
            char c1 = s.charAt(right);
            //推动窗口的右边界
            right++;
            //如果是目标字符则要统计起来
            if (target.containsKey(c1)) {
                window.put(c1, window.getOrDefault(c1, 0) + 1);
                if (window.get(c1).equals(target.get(c1))) {
                    valid++;
                }
            }
            System.out.println(window);
            //当字符出现的次数都满足的时候，说明窗口已经符合要求了，可以进行收缩。
            while (valid == target.size()) {
                //如果长度有效
                if (right - left < strLength) {
                    start = left;
                    strLength = right - left;
                }
                char c2 = s.charAt(left);
                //左边窗口进行收缩
                left++;
                //如果是目标字段，需要进行移除
                if (target.containsKey(c2)) {
                    //如果此时的目标字段个数和遍历结果的个数一样，去除的时候需要把有效个数减一
                    if (target.get(c2).equals(window.get(c2))) {
                        valid--;
                    }
                    window.put(c2, window.get(c2) - 1);
                }
            }
        }
        return strLength == Integer.MAX_VALUE ? "" : s.substring(start, start + strLength);
    }

    public static void main(String[] args) {
        minWindow("ADOBECODEBANC","ABC");
    }
}
//leetcode submit region end(Prohibit modification and deletion)
